πŸ‘©β€πŸ’» 42890. 후보킀

@Seongukbaek Posted June 02, 2022 Β· Updated June 02, 2022 Β· 3 min read

문제

Programmers - 후보킀

πŸ“ Logic

private void combination(int idx, int start, int keySize, HashSet<Integer> keys, int n, String[][] relation) { if (idx == keySize) { // 이미 뽑은 후보킀라면 μ œμ™Έ(μœ μΌμ„±, μ΅œμ†Œμ„± 검사), keys에 keyκ°€ ν¬ν•¨λœλ‹€λ©΄ μ΅œμ†Œμ„± 만쑱 X for (HashSet<Integer> key : candidateKeys) if (keys.containsAll(key)) return; // 뽑은 ν›„λ³΄ν‚€μ˜ 인덱슀λ₯Ό ν™•μΈν•˜μ—¬ μœ μΌμ„±μ„ 확인할 set HashSet<String> spareKeys = new HashSet<>(); for (String[] rel : relation) { StringBuilder sb = new StringBuilder(); // 선택(keys에 μΆ”κ°€)ν•œ 속성 체크 for (int k : keys) sb.append(rel[k]); spareKeys.add(sb.toString()); } // map의 크기와 relation의 길이가 κ°™λ‹€λ©΄ λͺ¨λ“  νŠœν”Œμ— λŒ€ν•΄μ„œ μ€‘λ³΅λœ 값이 μ—†λ‹€λŠ” μ˜λ―Έμ΄λ―€λ‘œ 후보킀가 될 수 있음 if (spareKeys.size() == relation.length) candidateKeys.add(keys); } else { for (int i = start; i < n; i++) { HashSet<Integer> selectedKeys = new HashSet<>(keys); selectedKeys.add(i); combination(idx + 1, i + 1, keySize, selectedKeys, n, relation); } } }
  • 후보킀λ₯Ό μƒμ„±ν•˜λŠ” ν•¨μˆ˜
  • μœ μΌμ„±κ³Ό μ΅œμ†Œμ„±μ„ λ§Œμ‘±ν•˜λŠ” 후보킀λ₯Ό candidateKeys 에 μΆ”κ°€ν•œλ‹€.

    • λ§Œλ“  후보킀에 ν•΄λ‹Ήν•˜λŠ” μ†μ„±κ°’μœΌλ‘œ Map 을 λ§Œλ“€μ—ˆμ„λ•Œ, 쀑볡없이 relation 수만큼 λ§Œλ“€μ–΄μ§„λ‹€λ©΄ 이λ₯Ό λ§Œμ‘±ν•˜λŠ” 후보킀이닀.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { // 후보킀듀을 μ €μž₯ν•  ArrayList static ArrayList<HashSet<Integer>> candidateKeys = new ArrayList<>(); public int solution(String[][] relation) { int n = relation[0].length; // 1κ°œλΆ€ν„° nκ°œκΉŒμ§€μ˜ 후보킀 생성 μ‹œλ„ for (int i = 0; i < n; i++) combination(0, 0, i + 1, new HashSet<>(), n, relation); return candidateKeys.size(); } private void combination(int idx, int start, int keySize, HashSet<Integer> keys, int n, String[][] relation) { if (idx == keySize) { // 이미 뽑은 후보킀라면 μ œμ™Έ(μœ μΌμ„±, μ΅œμ†Œμ„± 검사), keys에 keyκ°€ ν¬ν•¨λœλ‹€λ©΄ μ΅œμ†Œμ„± 만쑱 X for (HashSet<Integer> key : candidateKeys) if (keys.containsAll(key)) return; // 뽑은 ν›„λ³΄ν‚€μ˜ 인덱슀λ₯Ό ν™•μΈν•˜μ—¬ μœ μΌμ„±μ„ 확인할 set HashSet<String> spareKeys = new HashSet<>(); for (String[] rel : relation) { StringBuilder sb = new StringBuilder(); // 선택(keys에 μΆ”κ°€)ν•œ 속성 체크 for (int k : keys) sb.append(rel[k]); spareKeys.add(sb.toString()); } // map의 크기와 relation의 길이가 κ°™λ‹€λ©΄ λͺ¨λ“  νŠœν”Œμ— λŒ€ν•΄μ„œ μ€‘λ³΅λœ 값이 μ—†λ‹€λŠ” μ˜λ―Έμ΄λ―€λ‘œ 후보킀가 될 수 있음 if (spareKeys.size() == relation.length) candidateKeys.add(keys); } else { for (int i = start; i < n; i++) { HashSet<Integer> selectedKeys = new HashSet<>(keys); selectedKeys.add(i); combination(idx + 1, i + 1, keySize, selectedKeys, n, relation); } } } }

✏️ Review

  • μ‘°ν•©κ³Ό 집합에 λŒ€ν•œ λ¬Έμ œμž„μ€ λ°”λ‘œ λ– μ˜¬λ¦΄ 수 μžˆμ—ˆμ§€λ§Œ "μœ μΌμ„±" κ³Ό "μ΅œμ†Œμ„±" 을 λ§Œμ‘±ν•˜λŠ” 후보킀λ₯Ό κ΅¬ν˜„ν•˜λŠ”λ°μ—μ„œ λ§‰ν˜”λ‹€ ..
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€